package algorithm.middle;

import javax.print.attribute.IntegerSyntax;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
 * <p>
 * 我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
 * <p>
 * 所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
 * <p>
 * 请你返回「表现良好时间段」的最大长度。
 */
public class LongestWPI1124 {

    public int longestWPI(int[] hours) {
        //转换为前缀和问题。分别为1和-1
        int[] arr = new int[hours.length+1];
        Deque<Integer> deque = new LinkedList<>();
        //这个0代表着，计算时某个位置前缀和本身。
        deque.push(0);
        for (int i = 0; i < hours.length; i++) {
            if (hours[i] > 8) {
                arr[i+1] = arr[i]+1;
            } else {
                arr[i+1] = arr[i] - 1;
            }
            if (arr[i + 1] < arr[deque.peek()]) {
                deque.push(i + 1);
            }
        }
        //寻找最长子数组，s[i]-s[j]>0
        //单调栈.从后往前便利
        int res = 0;
        for (int i = arr.length - 1; i >= 0; i--) {
            while (!deque.isEmpty() && arr[deque.peek()] < arr[i]) {
                res = Math.max(res, i - deque.pop());
            }
        }
        return res;
    }
}
